public class code3 {
//    力扣 150 二叉树中的最大路径和
    // 这道题还有最核心的一点就是要理解什么是最大贡献值
    // 最大贡献值: 具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

    int maxNum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        // 创建一个方法实现递归操作

        // 因为要找到树节点中的最大值，此时我们需要向方法中传递一个 极小值 用于判断
        getMax(root);
        return maxNum;
    }

    public int getMax(TreeNode root) {
        // 这里使用的是 后序遍历 (目的就是为了先得到 左右 子树的节点，最后达到题目要求获得 左+右+根 的值)

        // 当当前 null 的时候，此时就表明已经找到的子树的节点(也就是达到的树的最深处)
        if(root == null) {
            return 0;
        }

        // 尝试获取左右节点的最大值
        // 这里直接传入的是节点，是要从一开始就找到子树节点
        // 对于这里节点的值在后面进行处理
        // 整体的方向是 自下而上
        // 这里直接排除了 负数 值，直接就换成了 0 (这并不会影响最大值)
        int left = Math.max(getMax(root.left), 0);
        int right = Math.max(getMax(root.right), 0);

        // 处理数据
        // 计算获取最大值
        // 当前节点加上左右子树的值
        int num = root.val + left + right;

        // 处理跟新最大值
        maxNum = Math.max(maxNum, num);

        // 返回当前节点和其 子节点 的最大的左右节点的值加和，跟新贡献值
        return root.val + Math.max(left, right);
    }
}
